#!/usr/bin/env python3

"""
Reverse a linked list from position m to n. Do ti in one-pass
Note: 1 <= m <= n length of list
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def link(self, node):
        self.next = node
        return node

    def show(self, end='\n'):
        print(str(self.val), end=' ')
        if self.next:
            self.next.show(' ')
        print(end=end)

class Solution:
    def reverse_between(self, head, m, n):
        if m == n:
            return head
        length = 1
        current = head
        last_node = None
        last_not_reversed_node = None
        first_reversed_node = None
        while current is not None:
            next_current = None
            if first_reversed_node is not None:
                tmp = current.next
                current.next = last_node
                next_current = tmp
                if length == n:
                    first_reversed_node.next = tmp
                    if last_not_reversed_node is not None:
                        last_not_reversed_node.next = current
                    else:
                        head = current
                    break
            elif length == m:
                first_reversed_node = current
                if last_node is not None:
                    last_node.next = None
            else:
                last_not_reversed_node = current
            last_node = current
            if next_current:
                current = next_current
            else:
                current = current.next
            length += 1
        return head



if __name__ == '__main__':
    s = Solution()
    head = ListNode(1)
    head.link(ListNode(2)).link(ListNode(3)).link(ListNode(4)).link(ListNode(5))
    head.show()

    result = s.reverse_between(head, 2, 4)
    result.show()
    
